{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一种典型做法：将 IPv4 地址（点分十进制）转换成 32 位无符号整数，把所有区间按起始地址排序，然后用二分查找快速定位。\n",
    "\n",
    "核心思路：\n",
    "\n",
    "1. **预处理区间**\n",
    "   - 将每个区间 `[start_ip, end_ip]` 的两端转换成整数。\n",
    "   - 按 `start_ip` 升序排序（题目保证区间互不重叠且闭区间）。\n",
    "2. **查询**\n",
    "   - 输入 IP，同样转换成整数。\n",
    "\n",
    "- 用 `std::upper_bound` 找到首个 `start_ip > query_ip` 的区间，然后看前一个区间是否包含该 IP。\n",
    "- 时间复杂度 `O(log N)`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "说明\n",
    "\n",
    "- `ipv4_to_uint` 简单解析点分十进制，若需要处理异常情况可加更多校验。\n",
    "- 数据量大时可从文件或数据库读取，再调用 `sort_ranges`。\n",
    "- 查询时只需把字符串 IP 转换后调用 `find_city`，即可得到对应城市。\n",
    "- 若要支持 IPv6，则需要使用更大整数表示（例如 `std::array<uint8_t, 16>` 或专门的库），并改写比较逻辑。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- [ip_range_city_lookup.cpp](./ip_range_city_lookup.cpp)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
